/*
 * @lc app=leetcode.cn id=397 lang=cpp
 *
 * [397] 整数替换
 */

// @lc code=start
class Solution {
public:
//枚举
    int integerReplacement(int n) {
        if (n == 1) {
            return 0;
        }
        if (n % 2 == 0) {
            return 1 + integerReplacement(n / 2);
        }
        return 2 + min(integerReplacement(n / 2), integerReplacement(n / 2 + 1));
    }
};
// @lc code=end

/**
     * 二进制观察处理法
     * 实现思路:
     *      最快的移动就是遇到2的次幂(例如数字16  10000 -> 01000 -> 00100 -> 00010 -> 00001)
     *      将二进制一直左移 最右为0时可以直接移动(例如数字6  000110 -> 000011)
     *      最右位为1时需把1变成0, 再移动(例如数字9  001001 -> 001000)
     *      故最优解就是如何在迭代中减少出现末尾1(就是什么时候+1, 什么时候-1 来实现过程中最少出现01或11结尾)
     * 得出以下结论:
     *      若n的二进制为 xxxx10, 则下一次处理 n = n/2 次数+1
     *      若n的二进制为 xxxx01, 则下一次处理 n = n/2 次数+2(即需要先-1再除以2, 故这里是加2) n > 1
     *      若n的二进制为 xxxx11, 则下一次处理 n = n/2 +1 次数+2(即需要先+1再除以2, 故这里是加2) n > 3
     *      特殊情况: 数字3  000011, 000011 -> 000010 -> 000001(两次即可)
     * 边界条件: 000001 -> 答案为0
     */
    // public int integerReplacement(int n) {
    //     int ans = 0;
    //     while (n > 1){
    //         若为偶数, 直接减半. 最后两位为xxxx10, 下一次处理 n = n/2 次数+1
    //         if ((n & 1) == 0){
    //             ans++;
    //             n = n >> 1;
    //         } else if(n == 3) {
    //             特殊情况3, 特殊处理, n = 1 次数+2
    //             ans += 2;
    //             n = 1;
    //         } else if ((n & 3) == 3){
    //             最后两位为11, 即xxxx11, n = n/2 +1 次数+2(即需要先+1再除以2, 故这里是加2)
    //             ans += 2;
    //             n = n/2 +1;
    //         }else {
    //             最后两位为01, 即xxxx01, n = n/2 次数+2(即需要先-1再除以2, 故这里是加2)
    //             ans += 2;
    //             n = n/2;
    //         }
    //     }
    //     return ans;
    // }

